package sit.engreal.leetcode.problems900;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * <a href="https://leetcode.cn/problems/advantage-shuffle/">870. 优势洗牌</a>
 */
public class LeetCode870 {
    public int[] advantageCount(int[] nums1, int[] nums2) {
        final int n = nums1.length;
        final List<Integer> p1 = new ArrayList<>(n);
        final List<Integer> p2 = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            p1.add(i);
            p2.add(i);
        }


        p1.sort(Comparator.comparingInt(i -> nums1[i]));
        p2.sort(Comparator.comparingInt(i -> nums2[i]));

        final int[] answer = new int[n];
        int left = 0;
        int right = n - 1;
        for (int i = 0; i < n; i++) {
            final int v = nums1[p1.get(i)];
            if (v > nums2[p2.get(left)]) {
                answer[p2.get(left)] = v;
                left++;
            } else {
                answer[p2.get(right)] = v;
                right--;
            }
        }

        return answer;
    }

    public static void main(String[] args) {
        final LeetCode870 demo = new LeetCode870();
        System.out.println(Arrays.toString(
                demo.advantageCount(
                        new int[]{2, 7, 11, 15},
                        new int[]{1, 10, 4, 11}
                )
        ));

        System.out.println(Arrays.toString(
                demo.advantageCount(
                        new int[]{12, 24, 8, 32},
                        new int[]{13, 25, 32, 11}
                )
        ));
    }
}
